#include <iostream>
#include <string.h>
#include <vector>      // 添加 vector 头文件
#include <functional>  // 添加 functional 头文件
#include <string>      // 添加 string 头文件

using namespace std;

typedef enum{Link, Thread} NodeTag;

class TreeNode
{
private:
    char data;              //值
    TreeNode* leftChild;    //左孩子
    TreeNode* rightChild;   //右孩子
    NodeTag lTag, rTag;     //线索Tag

    friend class MyTree;    //树类
public:
    TreeNode(char, TreeNode*, TreeNode*, NodeTag, NodeTag);
    ~TreeNode();

    void printNode();
    
};

class MyTree
{
private:
     TreeNode* root;        //根指针
     bool isThread;         //线索二叉树标志

     TreeNode* copytree(TreeNode* node);
     void deletree(TreeNode* node);
     void precheck(TreeNode* node);
     void midcheck(TreeNode* node);
     void inOrderThreaded(); 
     void backcheck(TreeNode* node); 
     TreeNode* locatecheck(TreeNode* node,const char& v);
      int leafcheck(TreeNode* node); 
      int highcheck(TreeNode* node);
      int countHeightRecursive(TreeNode* node);
      bool nodethread(TreeNode* node);
      bool treethread(TreeNode* node);
      void inorderthreadcheck(TreeNode* node, TreeNode*& prev);
public:
    MyTree();               //无参构造
    MyTree(const char[]);   //构造函数
    MyTree(const MyTree&);  //拷贝函数
    ~MyTree();              //析构函数

    void preOrderTraverse();    //前序遍历
    void inOrderTraverse();     //中序遍历
    void postOrderTraverse();   //后序遍历
    int countLeaf();            //叶结点计数
    int countHeight();          //计算树的深度
    bool isThreadedTree();      //判断是否为线索二叉树
    bool inOrderThreading();    //线索化
    TreeNode& locateNode(const char&);  //结点定位
    TreeNode& preNode(const TreeNode&); //获取前驱结点
    TreeNode& nextNode(const TreeNode&);//获取后继结点

};


class HuffmanTree
{
private:
    //添加必要的数据成员
    struct HuffmanNode {
        int weight;          // 权重（重要度）
        char data;           // 节点字符表示（可选）
        HuffmanNode* left;
        HuffmanNode* right;
        
        HuffmanNode(int w, char d = '\0') : weight(w), data(d), left(nullptr), right(nullptr) {}
        HuffmanNode(int w, HuffmanNode* l, HuffmanNode* r) : weight(w), left(l), right(r) {}
    };
     HuffmanNode* root;
    std::vector<std::pair<int, std::string>> huffmanCodes; // 存储节点值和对应的编码

     // 私有辅助函数
    void generateHuffmanCodes();
    void generateCodesRecursive(HuffmanNode* node, std::string code);
    void deleteTree(HuffmanNode* node);
   
  
public:
    HuffmanTree(const int&,const int[]);    //构造函数
    ~HuffmanTree();     //析构函数

    //输出哈夫曼编码
    //格式为：每行输出一个节点，节点排序递减
    //节点1值：编码
    //节点2值：编码
    //....
    //cpp中未给出该函数，遵守输出格式规范
    void printHuffmanCodes();   

 
};


